package leetcode;

/**
 * First Missing Positive
 * 
 * @author zhujb
 *
 *         2017年8月31日
 */
public class leet041 {

	/**
	 * 取数组中没有的第一个正整数，数字特征为index+1· [1,1] return 2 ; [-1,1,3] return 2;
	 * 
	 * @param nums
	 * @return
	 */
	public int firstMissingPositive(int[] nums) {

		int l = nums.length;
		int i = 0;
		while (i < l) {

			// 在nums[i]>=1 <=n的情况下,如果 nums[i]!=i+1 交换 nums[i] 和 nums[nums[i]-1]

			int j = nums[i];
			if (j >= 1 && j <= l && j != i + 1 && j!=nums[j-1]) {
				nums[i] = nums[j - 1];
				nums[j - 1] = j;
			} else {
				i++;
			}
			
		}

		for (int j = 0; j < l; j++) {
			if (nums[j] != j + 1) {
				return j + 1;
			}
		}
		// 这个没有的吧
		return l + 1;
	}

	public static void main(String[] args) {

		leet041 leet41 = new leet041();

		int[] nums = { 1, 1, 3, 4, -1 };
		System.out.println(leet41.firstMissingPositive(nums));

	}
}
